1. Field of the Invention
The present invention relates to a Galois field arithmetic logic unit of a code error check and correct apparatus employed for recording and reproducing data on an optical disk.
2. Description of the Related Art
Recently, there has been achieved an intensive development of data record/reproduce apparatus using an optical disk. Although the optical disk memory generally enables there to be recorded therein a greater amount of data as compared with a magnetic disk, the recording medium of the optical disk memory has a disadvantage that a higher raw error rate results.
To overcome this difficulty, there has been commonly employed a method in which error correcting codes are added to data when recording the data so as to record both the data and the error correcting codes on an optical disk and then a data error is detected and is corrected by use of the error correcting codes when reproducing the recorded data. As such an error correcting code, the Reed-Solomon code with a Hamming distance d=about 17 has attracted attention these days.
For a decoding of the Reed-Solomon code, syndromes are first calculated from a received word and then an error location polynomial .sigma. (x) and an error value polynomial .omega. (x) are attained from the syndrome. Finally, an error location and an error value are estimated from these polynomials so as to effect a correction; however, due to the great Hamming distance, the decoding process becomes complicated and hence takes a long period of time; furthermore, a large circuit is necessary to implement the decoding process by means of a hardware system.
Since the calculation of the syndrome greatly influences the decode speed, parallel operation hardware is employed in many cases. In a case where a particularly high-speed operation is required, also the other processing is effected, not by such a pure hardware system, but by means of a micro-programming scheme.
In this case, there have been used algorithms such as the method of Berlekamp Massey or the Euclidean algorithm (of the mutual division) for the computations of the error location polynomial and the error value polynomial. In order to attain error locations from the error location polynomial, the Chien's algorithm is employed in which all the possible error locations are assigned to the error location polynomial. The error value is obtained by effecting a differential calculation of the error location polynomial and a calculation and a division of the error value polynomial.
The Chien's algorithm, the calculation of the differentiation of the error location polynomial, and the calculation of the error value polynomial each are associated with values of polynomials. Heretofore, as a method to effect a calculation of values of a polynomial, there has been utilized a method called the Horner's method in which the computation is reduced to a repetitious computation of a sum of products. (Refer to, for example, "High Speed Decoding of Reed-Solomon Codes" described in the U.S. Pat. No. 4,142,174 2/1979.)
Referring now to the accompanying drawings, a conventional Galois field arithmetic logic unit will be described. FIGS. 4 and 5 show portions of a Galois field arithmetic logic unit employed in a conventional code correction processing. In FIG. 4, the configuration includes a 0 element decision circuit 11, input pipeline registers 12, 13, 34, a memory 28, a Galois field multiplier unit 29, a Galois field add circuit (exclusive OR logic circuit) 30, switch logic gate circuits 31, 32, and a power generate circuit generating a power of a primitive element .alpha. (location generate circuit) 33. The arithmetic operation is effected in GF(2.sup.r).
A received word is first deinterleaved and the resultant word is inputted to a code error detect circuit, namely, a syndrome calculate circuit. If all syndromes thus attained is other than 0, an occurrence of an error is assumed and the syndromes are delivered to the Galois arithmetic logic unit effecting an estimation of the number of errors and computations for coefficients of the error location polynomial, thereby computing the error locations based on the results.
The memory 28 is supplied with syndromes of which the number is represented by (Hamming distance-1) from the syndrome calculate circuit, and then the number t of errors and the t+1 coefficients of the respective degrees of the error location polynomial are computed and are then stored by means of the multiplier 29, the adder 30, a control logic circuit using a microprogram (not shown), an inverse element memory, and the like. Thereafter, also using the same Galois arithmetic logic unit, the root of the error location polynomial is computed according to the Chien's method.
Assuming for simplification that there exist two errors, in order to attain the root of the error location polynomial, the switch logic gate circuit 31 is changed over to the side of the adder 30 of the Galois arithmetic logic unit, the switch logic gate circuit 32 is set to the side of the location value generate circuit (primitive element generator) 33, coefficients k.sub.2, k.sub.1, k.sub.0, k.sub.2, k.sub.1, k.sub.0, etc. are sequentially assigned to the pipeline registers Rc 34 and Rb 13, and 0, .alpha..sup.0, .alpha..sup.0, 0, .alpha..sup.1, .alpha..sup.1, etc. are sequentially assigned to the pipeline register Ra 12 from the primitive element generator 33. Outputs from the adder 30 are, after the pipeline operation is completed, expressed as follows. EQU k.sub.2 +@*0 EQU k.sub.1 +(k.sub.2)*.alpha..sup.0 EQU k.sub.0 +(k.sub.1 +k.sub.2 *.alpha..sup.0)*.alpha..sup.0 EQU k.sub.2 +@*0 EQU k.sub.1 +(k.sub.2)*.alpha..sup.1 EQU k.sub.0 +(k.sub.1 +k.sub.2 *.alpha..sup.1)*.alpha..sup.1
Namely, the root of the error location polynomial should be judged for every third operation. Incidentally, the expressions above each are executed in a Galois field in which the operators + and * respectively indicate an addition and a multiplication and @ denotes an undefined number. FIG. 5 shows an internal structure of the multiplier circuit 29. This configuration includes multipliers 1-8 for multiplying fixed coefficients of a Galois field, and AND circuits 9 for multiplying the output from each fixed coefficient multiplier by the 0 source when each corresponding bit of the pipeline register 12 is 0, in other words the AND circuits 9 each disposed for every bit of the output from the fixed coefficient multiplier. Reference numeral 10 designates a parity generate circuit which effects an odd/even parity decision for each degree of the binary vector expression of all the symbols obtained as a result of the multiplication.
In the constitution above, however, as the number of error occurrences increases, the degrees respectively of the error location polynomial and the error value polynomial become greater, which leads to a problem that the amount of calculations of sum of products to obtain the values of the polynomials is increased and hence the decoding time becomes longer.
For instance, in an example where the code length n=130 and the number of errors t=8, let us consider the computation steps of the calculation of sum of products necessary to attain the error locations X0,--, X7 from the error location polymonials .sigma.(X).
According to the Chien's algorithm, the possible error locations are sequentially assigned to the error location polynomial so as to obtain a result in which the value of the polynomial is 0. Since the number of errors is t, the polynomial .sigma.(X) is of a t-degree polynomial, and t+1 steps are required to calculate the value of the expression by assigning a location xi of each error to the error location polynomial; furthermore, under the worst condition, the error locations are to be checked as many times as there are codes, namely,
(t+1)*n=9.multidot.130=1170 steps are required in total.
Similarly, the error value e.sub.i can be calculated, assuming the error location polynomial and the error value polynomial to be .omega.(X) and .sigma.'(X), respectively, from EQU e.sub.i =-.alpha..sup.i .multidot..omega.(.alpha..sup.i).multidot..sigma.'(.alpha..sup.i).sup.-1
However, since .omega.(.alpha..sup.i) and .sigma.'(.alpha..sup.i) must be computed as polynomical calculations, it is clear that the amount of the computation of sum of products is increased as the number of error occurrences becomes greater.